package data_structure.linkedList;

import java.util.ArrayList;

/**
 * @Name : data_structure.linkedList.JosephusCircle
 * @Description : 描述
 * Created by cyd on 2021-01-28 11:33:46
 */
public class JosephusCircle {
    private HeroNode head = new HeroNode(0, "头节点", "头节点");
    private ArrayList<HeroNode> heroList = new ArrayList<>();

    //初始化，构造器
    public JosephusCircle(Integer length) {
        head.setNext(head);
        for (int i = 0; i < length; i++) {
            add(new HeroNode(i + 1, "第" + (i + 1) + "个节点", ""));
        }
    }

    // 判断为空的方法
    public boolean isEmpty() {
        return head.getNext() == head;
    }

    // 找到最后一个节点的方法
    private HeroNode getEndNode() {
        HeroNode temp = head;
        while (temp.getNext() != head) {
            temp = temp.getNext();
        }
        return temp;
    }

    // 增加的方法
    private void add(HeroNode node) {
        HeroNode endNode = getEndNode();
        endNode.setNext(node);
        node.setNext(head);
    }

    // 按照索引找到前一个节点的方法
    private HeroNode selectPreNodeByNo(Integer no) {
        if (isEmpty()) {
            return head;
        }

        int i = no - 1;
        while (i < no) {
            HeroNode temp = head;
            while (temp.getNext() != head) {
                temp = temp.getNext();
                if (temp.getNo().equals(i)) {
                    return temp;
                }
            }
            i--;
            // 小于0，是为了保证no=1时的运行
            if (i <= 0) {
                break;
            }
        }
        return head;
    }

    // 按照索引删除某个节点，并加入list的方法，返回下一个节点
    private HeroNode deleteByIndex(Integer index) {
        HeroNode preNode = selectPreNodeByNo(index);
        HeroNode currentNode = preNode.getNext();
        // 删除的动作
        preNode.setNext(currentNode.getNext());
        // 添加到list
        heroList.add(currentNode);
        return preNode.getNext();
    }

    // 展示方法
    public void show() {
        if (isEmpty()) {
            return;
        }

        HeroNode temp = head;
        System.out.println(temp);
        while (temp.getNext() != head) {
            System.out.println(temp.getNext());
            temp = temp.getNext();
        }
    }

    // 从当前节点开始，数k下删除一个节点，返回被删除的下一个节点
    private HeroNode deleteK(HeroNode currentNode, Integer k) {
        assert currentNode != null : true;
        for (int i = 1; i < k; i++) {
            currentNode = currentNode.getNext();
            // 头节点不能进入删除的循环
            if (currentNode == head) {
                currentNode = currentNode.getNext();
            }
        }
        return deleteByIndex(currentNode.getNo());
    }


    // 从第x个节点开始数，每个数k个，删除第k个节点，循环执行直到循环链表为空
    public void handleJosephusQuestion(Integer x, Integer k) {
        // 得到第x个节点
        HeroNode xNode = selectPreNodeByNo(x).getNext();


        while (!isEmpty()) {
            //if (xNode == head) xNode = xNode.getNext();
            // 执行删除动作
            HeroNode nextNode = deleteK(xNode, k);
            // 头节点不参与删除循环
            if (nextNode == head) {
                nextNode = nextNode.getNext();
            }
            // 将被删除的节点的下一个节点，置为xNode
            xNode = nextNode;
        }
        System.out.println(heroList);
    }

    public static void main(String[] args) {
        JosephusCircle josephusCircle = new JosephusCircle(41);
//        josephusCircle.show();
//        System.out.println("-----------删除索引为5的节点------------");
//        josephusCircle.deleteByIndex(5);
//        josephusCircle.show();
//        System.out.println("-----------查询索引为3的节点------------");
//        System.out.println(josephusCircle.selectPreNodeByNo(3).getNext());
//        System.out.println(josephusCircle.heroList);
        System.out.println("------------从第1个节点开始，每次数5-----------------");
        josephusCircle.handleJosephusQuestion(1, 5);

    }
}
